"""
题目：判断一个单链表中是否存在环（即某个节点的 next 指针指向之前的节点）。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head):
    if not head or not head.next:  # 空链表或只有一个节点，不可能有环
        return False

    # 初始化快慢指针
    slow = head  # 慢指针，每次走一步
    fast = head.next  # 快指针，每次走两步

    # 当快慢指针不相遇时，继续遍历
    while slow != fast:
        # 如果快指针到达末尾，说明没有环
        if not fast or not fast.next:
            return False
        slow = slow.next  # 慢指针前进一步
        fast = fast.next.next  # 快指针前进两步

    # 如果快慢指针相遇，说明有环
    return True


# 测试
# 测试1：无环链表
head1 = create_linked_list([1, 2, 3, 4, 5])
print(has_cycle(head1))  # 输出: False

# 测试2：有环链表（手动创建环）
head2 = create_linked_list([1, 2, 3, 4, 5])
# 创建环：让最后一个节点指向第二个节点
current = head2
while current.next:
    current = current.next
current.next = head2.next  # 形成环
print(has_cycle(head2))  # 输出: True


# 辅助函数（复用之前的创建链表函数）
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head
